package cn.hughie.tree;

import java.util.Deque;
import java.util.LinkedList;
/**
 * 红黑二叉查找树
 *
 * @author yuh
 * @date 2018/5/17 17:29
 */
public class RedBlackBST<K extends Comparable<K>, V> {


    /**
     * 表示到达指定节点的链是红色
     */
    private static boolean RED = true;
    /**
     * 表示到达指定节点的链是黑色
     */
    private static boolean BlACK = false;

    /**
     * 节点
     */
    private class Node {
        Node left;
        Node right;
        int n;
        K key;
        V value;
        boolean color;

        public Node(K key, V value, boolean color) {
            this.key = key;
            this.value = value;
            this.color = color;
        }

        public Node() {
        }
    }

    /**
     * root为根节点
     */
    private Node root;

    /**
     * 插入元素
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        root = put(root, key, value);
        root.color = BlACK;
    }

    /**
     * 返回总节点数目
     *
     * @return
     */
    public int size() {
        return size(root);
    }

    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        return size(node.left) + size(node.right) + 1;
    }

    /**
     * 插入节点到node的子树
     *
     * @param node
     * @param key
     * @param value
     */
    public Node put(Node node, K key, V value) {
        if (node == null) {
            return new Node(key, value, RED);
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = put(node.right, key, value);
        } else if (cmp < 0) {
            node.left = put(node.left, key, value);
        } else {
            node.value = value;
        }
        //旋转调整满足红黑树要求
        if (isRed(node.right) && !isRed(node.left)) {
            node = rotateL(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateR(node);
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }
        node.n = size(node.left) + size(node.right) + 1;

        return node;
    }

    /**
     * 是否是红节点
     *
     * @param node
     * @return
     */
    private boolean isRed(Node node) {
        if (node == null) {
            return BlACK;
        }
        return node.color == RED;
    }

    /**
     * 左旋 转移到右字节的左子节点
     *
     * @param h
     * @return
     */
    private Node rotateL(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = size(h.left) + size(h.right) + 1;
        return x;
    }

    /**
     * 右旋 转移到左子节点的右节点
     *
     * @param h
     * @return
     */
    private Node rotateR(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.n = h.n;
        h.n = size(h.left) + size(h.right) + 1;
        return x;
    }

    /**
     * @param node 反色左右子树
     */
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BlACK;
        node.right.color = BlACK;
    }

    /**
     * 全树最小元素
     *
     * @return
     */
    public K min() {
        return min(root).key;
    }


    /**
     * node子树最小元素
     *
     * @param node
     * @return
     */
    public Node min(Node node) {
        if (node == null) {
            return null;
        }

        if (node.left == null) {
            return node;
        }
        return min(node.left);

    }

    /**
     * 全树最大元素
     *
     * @return
     */
    public K max() {
        return max(root).key;
    }


    /**
     * node子树最大元素
     *
     * @param node
     * @return
     */
    public Node max(Node node) {
        if (node == null) {
            return null;
        }

        if (node.right == null) {
            return node;
        }
        return max(node.right);

    }

    /**
     * 可迭代的K
     *
     * @return
     */
    public Iterable<K> keys() {
        return keys(min(), max());
    }


    /**
     * 创建队列
     *
     * @param min
     * @param max
     * @return
     */
    public Iterable<K> keys(K min, K max) {
        Deque<K> deque = new LinkedList<>();
        keys(root, deque, min, max);
        return deque;
    }

    /**
     * 中序遍历
     *
     * @param node
     * @param deque
     * @param min
     * @param max
     */
    public void keys(Node node, Deque<K> deque, K min, K max) {

        if (node == null) {
            return;
        }

        int cmplo = min.compareTo(node.key);
        int cmphi = max.compareTo(node.key);

        if (cmplo < 0) {
            keys(node.left, deque, min, max);
        }
        if (cmplo <= 0 && cmphi >= 0) {
            deque.addLast(node.key);
        }
        if (cmphi > 0) {
            keys(node.right, deque, min, max);
        }
    }

    public static void main(String[] args) {
        RedBlackBST<Integer, Integer> treeMap = new RedBlackBST<>();
        for (int i = 0; i < 10; i++) {
            treeMap.put(i, i);
        }
        Iterable<Integer> keys = treeMap.keys();
        System.out.println(keys);
    }


}
